1462. 课程表 IV

Similar Question

Solution Tips

方案一: BFS + 拓扑排序

var checkIfPrerequisite = function(numCourses, prerequisites, queries) {
    let adjList = new Array(numCourses).fill(0).map(() => new Array());
    let indgree = new Array(numCourses).fill(0);
    let isPre = new Array(numCourses).fill(0).map(() => new Array(numCourses).fill(false));
    for (let p of prerequisites) {
        ++indgree[p[1]];
        adjList[p[0]].push(p[1]);
    }
    let queue = [];
    for (let i = 0; i < numCourses; ++i) {
        if (indgree[i] == 0) {
            queue.push(i);
        }
    }

    while (queue.length) {
        let cur = queue.shift();
        for (let neighbor of adjList[cur]) {
            isPre[cur][neighbor] = true;
            // 把中间的 path 也补充上, 这一步是最难想的
            for (let i = 0; i < numCourses; ++i) {
                isPre[i][neighbor] = isPre[i][neighbor] || isPre[i][cur];
            }
            --indgree[neighbor];
            if (indgree[neighbor] == 0) {
                queue.push(neighbor);
            }
        }
    }
    res = [];
    for (let query of queries) {
        res.push(isPre[query[0]][query[1]]);
    }
    return res;
};